package mid.class1;

import common.ArrayUtils;

import java.util.Arrays;

/**
 * 前缀特征:
 * 说明; a[n]-a[n-1]的值，就是前缀特征
 * a数组的特征:
 * [3, 6, 12, 20]  3，6，8  (6-3,12-6,20-12)
 * [1, 9]          8 (9-1)
 * [4, 7, 2]       3,-5 (7-4,2-7)
 * [1, 4,-1]       3,-5 (4-1,-1-4)
 * <p>
 * b数组的特征:
 * [2, 5]          3 (5-3)   , 数能匹配到a的3个组
 * [7, 10, 5]      3,-5 (10-7,5-10)，数能匹配到a的2个组
 * <p>
 * 问b的特征能匹配上a?
 */
public class Code07_countConsistentKeys {
    public static void main(String[] args) {
        int[][] a = new int[][]{
                {3, 6, 12, 20},
                {1, 9},
                {4, 7, 2},
                {1, 4, -1}};
        int[][] b = new int[][]{
                {2, 5},
                {7, 10, 5}};

        countConsistentKeys(a, b);
    }

    /**
     * 求b特征匹配到的最大数量
     */
    private static void countConsistentKeys(int[][] a, int[][] b) {
        ArrayTrie trie = new ArrayTrie();
        StringBuilder builder = new StringBuilder();

        for (int[] nums : a) {
            builder.setLength(0);
            for (int i = 1; i < nums.length; i++) {
                builder.append((nums[i] - nums[i - 1]) + "#");
            }
            trie.insert(builder.toString());
        }

        int k = 0;
        int[] ans = new int[b.length];
        for (int[] nums : b) {
            builder.setLength(0);
            for (int i = 1; i < nums.length; i++) {
                builder.append((nums[i] - nums[i - 1]) + "#");
            }
            ans[k++] = trie.count(builder.toString());
        }
        ArrayUtils.printArr(ans);
        trie.clear();
    }

    private static class ArrayTrie {
        private int m = 12;
        public int[][] tree = new int[m][m];
        public int[] pass = new int[m + 1];
        private int cnt = 0;

        public ArrayTrie() {
            this.cnt = 1;
        }

        public int path(char c) {
            if (c == '#') {
                return 10;
            } else if (c == '-') {
                return 11;
            } else {
                return c - '0';
            }
        }

        public void insert(String world) {
            int cur = 1;
            pass[cur]++;
            for (int i = 0; i < world.length(); i++) {
                int path = path(world.charAt(i));
                if (tree[cur][path] == 0) {
                    tree[cur][path] = ++cnt;
                }
                cur = tree[cur][path];
                pass[cur]++;
            }
        }

        public int count(String world) {
            int cur = 1;
            for (int i = 0; i < world.length(); i++) {
                int path = path(world.charAt(i));
                if (tree[cur][path] == 0) {
                    return 0;
                }
                cur = tree[cur][path];
            }
            return pass[cur];
        }

        public void clear() {
            for (int i = 0; i < cnt; i++) {
                Arrays.fill(tree[i], 0);
                pass[i] = 0;
            }
        }
    }
}
